package e_ch13_directedG.topoSort;

import java.util.ArrayList;

public class GraphDFS {

    private Graph G;
    private boolean[] visited;

    private ArrayList<Integer> pre = new ArrayList<>();
    private ArrayList<Integer> post = new ArrayList<>();

    public GraphDFS(Graph G){

        this.G = G;
        visited = new boolean[G.V()];
        for(int v = 0; v < G.V(); v ++)  //遍历 O(E+V); 因为该层for循环把所有V过了一遍，对所有连通分量进行dfs 等价于把所有E过了一遍，所以总体时间复杂度是V+E；虽然E是用V表示的，但是这只是存储方式而已，E就是E，和V是不一样的；
            if(!visited[v])
                dfs(v);
    }

    private void dfs(int v){  	//目前讨论的图跟树就是一回事，只不过树没有回路；
    		//递归终止条件应该是 v是空白，也就是v不在图里；但是图不像树，树的邻接节点是直接定义成成员变量的，这里想判断 首先就得在最后一个节点再递归一层过来，但事实上如果没有节点了[空]， 遍历子节点的foreach就直接结束了 没办法再递归一层，直接就自己结束递归了，所以这里的条件不用写，而是在最后一个节点的那一层递归就结束。
        visited[v] = true;
        pre.add(v);
        for(int w: G.adj(v))
            if(!visited[w])
                dfs(w);
        post.add(v);
    }

    public Iterable<Integer> pre(){ //Iterable<Integer>返回接口类型，隐藏实现细节，扩展性更强；
        return pre;
    }

    public Iterable<Integer> post(){
        return post;
    }
    
    public static void main(String[] args){

        Graph g = new Graph("g.txt");
        GraphDFS graphDFS = new GraphDFS(g);
        System.out.println("DFS preOrder : " + graphDFS.pre());
        System.out.println("DFS postOrder : " + graphDFS.post());
    }
}
